The invention relates to fingerprint coding and recognition and retrieval systems based on generally invarying topological irregularities, characteristics or minutiae (which terms are used interchangeably herein) of fingerprints. The term "fingerprint" or "print" is used in reference to the epidermal ridge lines of the ten fingers of the human hand, palm prints, toe and sole prints of humans wherein such epidermal ridge lines and characteristic features thereof are in patterns unique to a particular individual.
In my paper entitled "Digital Coding of Single Fingerprints--A New Approach for the Computer Age", Journal of Police Science and Administration, Vol. X, No. 2, June 1982, I show that the soft elastic nature of human skin causes substantial variation of the spatial descriptions of successive impressions of the same fingerprints. Consequently, spatially based coding schemes used for forming machine searchable databases have inherent inaccuracies due to the fact that the spatial based coordinate system typically used for coding purposes could not take into account the wide variations in spatial distortions making the match or identification between two rolled prints on the same finger somewhat problematical particularly where the prints are taken at substantially different times or pressures.
Topological coding schemes provide concise digital codes that provide a more economical and more reliable basis for ten print identification systems. In my above referred to paper, I suggest comparison methods based on topological coding of prints in which a topology base coding system for recording and comparing minutiae used vector arrays generated from topologically based coding of fingerprints.
According to this invention, each fingerprint is scanned by a scanning system which typically includes a scanning `line` which sweeps in a predetermined manner, such as horizontally, vertically or radially, from a prescribed origin for the scanning system utilized. When the scanning line moves over an irregularity (such as a ridge ending, bifurcation, etc.), the irregularity is recorded by the use of at least three coordinates: a type code (T) to particularly identify the irregularity, a measure (M) of the scanning line position when it hits the irregularity, and a ridge count (R) which is the number of ridges intersecting the scanning line, at that position, between the irregularity and a prescribed point on, or origin for, the scanning line. A collection of coordinates sets (T, M, R) uniquely specifies the topology of a fingerprint or any part thereof.
Thus, the present invention provides a system for recording a complete topological description of a fingerprint subject to the constraint that each characteristic be in a given database, recorded once and only once. To form a library or database of topological coordinate sets for search purposes, rolled or file prints or so-called ten-print cards, are utilized and a central point on the fingerprint, (such as a core) is selected as a center of a rotating ridge scan line. When the scan line is a rotating ridge scan line, the rotating ridge scan line, which preferably has a center of rotation or origin which is just off of any ridge, is relatively rotated in a predetermined scan direction, clockwise, for example, to different topological characteristics (sometimes called irregularities or minutiae) of the fingerprint for a plurality of ridge lines. A hexadecimal digital code representing the type (T) of irregularity (ridge-ending, bifurcation, etc.) and the angular coordinate (.theta.) (which corresponds to the measure (M) of scanning line position) of the irregularity is recorded. In this case, the angular coordinate (.theta.) is sufficient to specify the order in which the irregularities are passed over by the sweeping or rotating ridge scan line. The ridge count (R) between the characteristic or the irregularity and the central observation point specifies the ridge on which the irregularity occurs. Thus, a list of coordinates sets of the form (T, .theta., R) specifies the topology of any sector uniquely. A fourth coordinate is added to the coordinate set to correspond to the radial distance (D) measured from the central observation point. D and .theta. then specify the positions of the characteristics in space and the full coordinate set (T, .theta., R, D) gives a complete topological and spatial description of a fingerprint which only requires 4 bytes per irregularity.
Prints such as latent prints found at the scene of a crime (SOC) are coded according to the same topological coordinate scheme. Computerized searching of such a latent mark against a large established collection of file prints is then performed through reconstruction of the topology local to each characteristic followed by comparison of such localized topology.
Additionally, fast comparison of rolled prints can be conducted on the basis of extracted vectors.
Topological vector extraction is based in part on the system disclosed in my above referred to paper. The core of the fingerprint is centrally located at a reference point and a horizontal line is projected through the core to intersect ridge lines to each side of the centrally located reference point. In the case of an arch a vertical line is drawn through successive ridge summits. From the points of crossing of the ridges with the projected horizontal or vertical line, the ridges are traced to the first significant irregularity and a type code (T) is assigned to the irregularity and with the distance (D) from the reference line and these data are recorded in a predetermined order to constitute a topological vector for the print which then is recorded in a machine searchable database. Comparison of vectors take the form of a sequence of array operations. Comparison of good quality rolled prints is performed extremely rapidly on this basis.